Packet matching, which includes classification and forwarding, is a crucial function performed by Internet routers. Briefly, packet matching is concerned with the task of taking incoming packets to a router and determining how best to classify and how best to forward the packet based on the packet's header. Matching is generally accomplished the same way, namely the packet header is compared with a database, and the best match between the packet header and the entries of the database is found. The entries of the database may be classification rules, or they may be forwarding addresses, but the general procedure is the same. Furthermore, the goals of classification and forwarding are the same, that is finding the best match between the packet header and the database entries as quickly as possible.
In current routers, the databases, such as rule databases, contain anywhere from tens to around one thousand rules. These rules generally reside in high speed, solid state memory such as Content Addressable Memory (CAM) that allows quick, parallel, comparisons between an incoming packet and the contents of the memory. Today's most advanced routers can match up to around 10 million packets per second. While current solutions works well for rule databases of up to around one thousand rules, the current solutions do not scale up adequately for the requirements of next generation routers.
Next generation routers will maintain rule databases containing 32,000 or more rules. The increased speed of these new routers will require packet matching speeds of 100 million or more packets per second. Power dissipation becomes a major problem at these speeds. A parallel search of the databases requires that every bit of the memories upon which the databases reside be simultaneously accessed. This places excessive demands on the router's power distribution system, greatly complicating the layout and routing of the memory chips and printed circuit boards comprising the router, and significantly taxing the cooling systems employed by the router. Any conventional solutions to these problems adversely impact the cost of the router. While a more linear search can be performed on the databases, any reduction in parallelism adversely impacts the router's speed, which is limited by the packet matching speed.
Thus a need presently exists for a Packet Matching System and Method that can satisfy the packet matching needs of future routers while avoiding the limitations of present matching schemes.